package util;

/**
 * This class is based on {@link java.util.ArrayList}, but is specifically for storing longs.
 *
 * @author Neil Dickson
 */
public final class LongList implements java.util.RandomAccess, Cloneable, java.io.Serializable {
	/**
	 * The array holding the data of the IntList
	 * The capacity of the IntList is the length of this array.
	 */
	private transient long[] elementData;

	/**
	 * The size of the IntList (the number of elements it contains).
	 *
	 * @serial
	 */
	private int size;

	/**
	 * The number of times this list has been modified.
	 *
	 * This field is used by the {@link #writeObject} function to determine whether the list was modified
	 * while writing out the object.
	 */
	private transient int modCount;

	/**
	 * Constructs an empty list with the specified initial capacity.
	 *
	 * @param initialCapacity the initial capacity of the list
	 * @throws IllegalArgumentException if the specified initial capacity is negative
	 */
	public LongList(int initialCapacity) {
		if (initialCapacity < 0) {
			throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
		}
		elementData = new long[initialCapacity];
		size = 0;
		modCount = 0;
	}

	/**
	 * Constructs an empty list with an initial capacity of ten.
	 */
	public LongList() {
		this(10);
	}

	/**
	 * Trims the capacity of this <tt>IntList</tt> instance to be the list's current size.
	 * An application can use this operation to minimize the storage of an <tt>IntList</tt> instance.
	 */
	public void trimToSize() {
		modCount++;
		int oldCapacity = elementData.length;
		if (size < oldCapacity) {
			long[] oldData = elementData;
			elementData = new long[size];
			System.arraycopy(oldData, 0, elementData, 0, size);
		}
	}

	/**
	 * Increases the capacity of this <tt>IntList</tt> instance, if necessary, to ensure that it can hold
	 * at least the number of elements specified by the minimum capacity argument.
	 *
	 * @param minCapacity the desired minimum capacity
	 */
	public void ensureCapacity(int minCapacity) {
		modCount++;
		int oldCapacity = elementData.length;
		if (minCapacity > oldCapacity) {
			long[] oldData = elementData;
			int newCapacity = (oldCapacity*3)/2 + 1;
			if (newCapacity < minCapacity) {
				newCapacity = minCapacity;
			}
			elementData = new long[newCapacity];
			System.arraycopy(oldData, 0, elementData, 0, size);
		}
	}

	/**
	 * @return the number of elements in this list
	 */
	public int size() {
		return size;
	}

	/**
	 * @return true iff this list has no elements
	 */
	public boolean isEmpty() {
		return size==0;
	}

	/**
	 * @param value value whose presence in this IntList is to be tested
	 * @return true iff the specified element is present
	 */
	public boolean contains(int value) {
		return indexOf(value) >= 0;
	}

	/**
	 * @param value value to search for
	 * @return index of the first occurrence of the value in this list, or -1 if the value is not found.
	 */
	public int indexOf(int value) {
		for (int i=0; i < size; i++) {
			if (value==elementData[i]) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * @param value value to search for
	 * @return index of the last occurrence of the value in this list, or -1 if the value is not found.
	 */
	public int lastIndexOf(int value) {
		for (int i = size-1; i>=0; i--) {
			if (value==elementData[i]) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * @return a copy of this <tt>IntList</tt>
	 */
	public LongList clone() {
		LongList that = new LongList(elementData.length);
		System.arraycopy(elementData, 0, that.elementData, 0, size);
		return that;
	}

	/**
	 * @return a new array containing all of the elements in this list in the correct order.
	 */
	public long[] toArray() {
		long[] result = new long[size];
		System.arraycopy(elementData, 0, result, 0, size);
		return result;
	}

	/**
	 * Copies the elements in this list into the given array in the correct order,
	 * or into a new array if the given array is too small.
	 *
	 * @param a the array into which the elements of the list are to be copied
	 * @return an array containing the elements of the list
	 */
	public long[] toArray(long[] a) {
		if (a.length < size) {
			return toArray();
		}
		System.arraycopy(elementData, 0, a, 0, size);
		return a;
	}

	/**
	 * @param index index of element to return
	 * @return value at the specified position in this list
	 * @throws IndexOutOfBoundsException if index is out of range <tt>(index &lt; 0 || index &gt;= size())</tt>
	 */
	public long get(int index) {
		RangeCheck(index);
		return elementData[index];
	}

	/**
	 * Replaces the element at the specified position in this list with the specified value.
	 *
	 * @param index index of element to replace.
	 * @param value value to be stored at the specified position.
	 * @return value previously at the specified position.
	 * @throws IndexOutOfBoundsException if index out of range <tt>(index &lt; 0 || index &gt;= size())</tt>.
	 */
	public long set(int index, long value) {
		RangeCheck(index);
		long oldValue = elementData[index];
		elementData[index] = value;
		return oldValue;
	}

	/**
	 * Appends the specified value to the end of this list.
	 *
	 * @param value value to be appended to this list
	 */
	public void add(long value) {
		ensureCapacity(size + 1);  // Increments modCount!!
		elementData[size++] = value;
	}

	/**
	 * Inserts the specified value at the specified position in this list.
	 * Shifts the element currently at that position (if any) and any subsequent elements to the right
	 * (adds one to their indices).
	 *
	 * @param index   index at which the specified value is to be inserted.
	 * @param value value to be inserted.
	 * @throws IndexOutOfBoundsException if index is out of range <tt>(index &lt; 0 || index &gt; size())</tt>.
	 */
	public void add(int index, long value) {
		if (index > size || index < 0) {
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
		}
		ensureCapacity(size + 1);  // Increments modCount!!
		System.arraycopy(elementData, index, elementData, index + 1, size - index);
		elementData[index] = value;
		size++;
	}

	/**
	 * Removes the element at the specified position in this list.
	 * Shifts any subsequent elements to the left (subtracts one from their indices).
	 *
	 * @param index the index of the element to removed.
	 * @return the value that was removed from the list.
	 * @throws IndexOutOfBoundsException if index out of range <tt>(index &lt; 0 || index &gt;= size())</tt>.
	 */
	public long removeElementAt(int index) {
		RangeCheck(index);
		long oldValue = elementData[index];
		fastRemove(index);
		return oldValue;
	}

	/**
	 * Removes the first occurrence of the specified value from this list
	 *
	 * @param value value to be removed from this list, if present
	 * @return true iff the list contained the specified element
	 */
	public boolean removeValue(long value) {
		for (int index = 0; index < size; index++) {
			if (value==elementData[index]) {
				fastRemove(index);
				return true;
			}
		}
		return false;
	}

	/**
	 * Private remove method that skips bounds checking and does not return the value removed.
	 *
	 * @param index index of the element to be removed
	 */
	private void fastRemove(int index) {
		modCount++;
		int numMoved = size - index - 1;
		if (numMoved > 0) {
			System.arraycopy(elementData, index + 1, elementData, index, numMoved);
		}
		--size;
	}

	/**
	 * Removes all of the elements from this list.
	 */
	public void clear() {
		modCount++;
		size = 0;
	}

	/**
	 * Appends all of the elements in the specified array to the end of this list, in order.
	 *
	 * @param a array of values to be inserted into this list
	 * @return true iff this list changed as a result of the call
	 */
	public boolean addAll(long[] a) {
		int numNew = a.length;
		ensureCapacity(size + numNew);  // Increments modCount
		System.arraycopy(a, 0, elementData, size, numNew);
		size += numNew;
		return numNew!=0;
	}

	/**
	 * Inserts all of the elements in the specified array into this list, starting at the specified position.
	 * Shifts the element currently at that position (if any) and any subsequent elements to the right
	 * (increases their indices).  The new elements will appear in the list in order.
	 *
	 * @param index index at which to insert first element from the specified array
	 * @param a array of values to be inserted into this list
	 * @return true iff this list changed as a result of the call
	 * @throws IndexOutOfBoundsException if index out of range <tt>(index &lt; 0 || index &gt; size())</tt>
	 */
	public boolean addAll(int index, long[] a) {
		if (index > size || index < 0) {
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
		}
		int numNew = a.length;
		ensureCapacity(size + numNew);  // Increments modCount
		int numMoved = size - index;
		if (numMoved > 0) {
			System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
		}
		System.arraycopy(a, 0, elementData, index, numNew);
		size += numNew;
		return numNew!=0;
	}

	/**
	 * Removes from this list all of the elements whose index is between fromIndex (inclusive) and toIndex (exclusive).
	 * Shifts any succeeding elements to the left (reduces their index).
	 * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
	 * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
	 *
	 * @param fromIndex index of first element to be removed.
	 * @param toIndex   index after last element to be removed.
	 */
	public void removeRange(int fromIndex, int toIndex) {
		modCount++;
		int numMoved = size - toIndex;
		System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
	}

	/**
	 * Checks if the given index is below the size limit.  If not, it throws IndexOutOfBoundsException.
	 * This method does *not* check if the index is negative: It is always used immediately prior to an array access,
	 * which throws an ArrayIndexOutOfBoundsException if index is negative.
	 */
	private void RangeCheck(int index) {
		if (index >= size) {
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
		}
	}

	/**
	 * Saves the state of the <tt>IntList</tt> to a stream.
	 *
	 * @serialData The length of the array backing the <tt>IndexOutOfBoundsException</tt>
	 * instance is written, followed by all of its elements in the proper order.
	 */
	private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
		int expectedModCount = modCount;
		// Write out element count, and any hidden stuff
		s.defaultWriteObject();
		// Write out array length
		s.writeInt(elementData.length);
		// Write out all elements in the proper order.
		for (int i = 0; i < size; i++) {
			s.writeLong(elementData[i]);
		}
		if (modCount!=expectedModCount) {
			throw new java.util.ConcurrentModificationException();
		}
	}

	/**
	 * Reconstitute the <tt>IntList</tt> instance from a stream.
	 * @see {@link #writeObject}
	 */
	private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
		// Read in size, and any hidden stuff
		s.defaultReadObject();
		// Read in array length and allocate array
		int arrayLength = s.readInt();
		elementData = new long[arrayLength];
		// Read in all elements in the proper order.
		for (int i = 0; i < size; i++) {
			elementData[i] = s.readLong();
		}
	}
}